package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.base.TreeNode;
import com.xsherl.leetcode.utils.PrintUtils;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PathSum2 {

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        pathSum(root, targetSum, new LinkedList<>(), res);
        return res;
    }

    public void pathSum(TreeNode root, int sum, LinkedList<Integer> path, List<List<Integer>> res){
        if (root == null){
            return;
        }
        sum -= root.val;
        path.addLast(root.val);
        if (root.left == null && root.right == null){
            if (sum == 0){
                res.add(new ArrayList<>(path));
            }
            path.removeLast();
            return;
        }
        pathSum(root.left, sum, path, res);
        pathSum(root.right, sum, path, res);
        path.removeLast();
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.buildTree(5,4,8,11,null,13,4,7,2,null,null,5,1);
        int target = 22;
        PrintUtils.println(root);
        List<List<Integer>> list = new PathSum2().pathSum(root, target);
        System.out.println(list);
    }
}
